"""
    在一个二维的花园中，有一些用 (x,  y) 坐标表示的树
    由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树
    只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标
    example 1:
     输入: [[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]]
     输出: true
    example 2:
     输入: [[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4]]
     输出: false
    example 3:
     输入: [[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]]
     输出: false
    example 4:
     输入: [[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]]
     输出: false
"""
import sys
from typing import List


# 解决这个问题，需要进行以下四个判断：
#   1、所有小矩形的面积之和，等于最终形成的大矩形的面积，若不是，则不能形成完美矩形；
#   2、遍历小矩形，判断其四个顶点的坐标，是否在已访问坐标集合中，若是，则移除这个坐标（即为消融）；若不是，则将这些顶点坐标加入到已访问坐标集合中；
#   3、最终如果能够形成完美矩形，那么已访问坐标集合中只能有四个元素，若集合中元素不是四个，则不能形成完美矩形；
#   4、判断最终形成的大矩形，其四个顶点是否就是已访问坐标集合中的四个元素，若是，则找到完美矩形。
# 首先，遍历所有小矩形，记录最左下和最右上的两个顶点坐标这两个坐标就表示了最终大矩形的顶点坐标
#       然后可以利用这个大矩形坐标，计算出大矩形面积，从而与小矩形的面积累加和进行判断，看两者是否相同。
# 其次，坐标消融，我们通过观察可以发现，当两个矩形拼在一起，形成一个更大形状的物体时，这两个矩形的相同坐标，表示两个小矩形的边缘部分触碰在了一起
#       这个边缘应该被消融，不再作为这个更大物体的顶点出现
#       只有这个大物体的边缘部分顶点，才能被保留
#       因此，我们设置一个已访问坐标集合，如果小矩形的顶点坐标出现在这个集合中，说明这个顶点需要被消融，那么就移出已访问坐标集合反之，则加入
#       因此，当所有的小矩形边缘被消融后，如果这些小矩形拼接在一起能形成一个大矩形，那么大矩形只能有四个顶点。
# 最后，将大矩形的最左下、右下、左上、右上的顶点，逐一判断是否为已访问坐标集合中的元素
#       因为题目中挖了一个坑，没有说明是否会出现两个小矩形完全重叠的情况
#       因此，最后的这个判断，就是为了解决这个坑而设置的
#       只有当大矩形的最左下、右下、左上、右上的顶点坐标，都是经过消融之后的、已访问坐标集合中的元素，才能表示，我们找到了一个完美矩形
def perfect_rectangle(rectangles: List[List[int]]) -> bool:
    X1, Y1, X2, Y2 = sys.maxsize, sys.maxsize, -sys.maxsize, -sys.maxsize
    sum_area, visited_points = 0, set()
    for x1, y1, x2, y2 in rectangles:
        X1, Y1, X2, Y2 = min(X1, x1), min(Y1, y1), max(X2, x2), max(Y2, y2)
        sum_area += (y2 - y1) * (x2 - x1)
        points = [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]
        for point in points:
            if point in visited_points:
                visited_points.remove(point)
            else:
                visited_points.add(point)
    expected_area = (Y2 - Y1) * (X2 - X1)
    if expected_area != sum_area:
        return False
    if len(visited_points) != 4:
        return False
    return all([large_point in visited_points for large_point in [(X1, Y1), (X2, Y2), (X1, Y2), (X2, Y1)]])


if __name__ == '__main__':
    print(perfect_rectangle([[1,  1,  3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]]))
    print(perfect_rectangle([[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4]]))
    print(perfect_rectangle([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]]))
    print(perfect_rectangle([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]]))